//LCR 011. 连续数组
/*给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。*/

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        int sum = 0;
        int ret = 0;
        hash[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0)
                sum--;
            else
                sum += nums[i];
            if (hash.count(sum)) {
                ret = max(ret, i - hash[sum]);
            }
            hash[sum] = hash.count(sum) ? hash[sum] : i;
        }
        return ret;
    }
};

//二叉树的最大深度
/*给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。*/
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        int sum = 0;
        int ret = 0;
        hash[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0)
                sum--;
            else
                sum += nums[i];
            if (hash.count(sum)) {
                ret = max(ret, i - hash[sum]);
            }
            hash[sum] = hash.count(sum) ? hash[sum] : i;
        }
        return ret;
    }
};